#include "tools.cpp"

class Solution {
  public:
    int maxDistance(vector<vector<int>>& grid) {
        std::array<std::pair<int, int>, 4> dir{std::make_pair(1, 0), std::make_pair(0, 1), std::make_pair(0, -1),
                                               std::make_pair(-1, 0)};
        std::queue<std::pair<int, int>> q;
        std::vector<std::vector<int>> paths(grid.size(), std::vector<int>(grid.front().size(), INT_MAX));
        for (int i = 0; i < grid.size(); ++i) {
            for (int j = 0; j < grid.front().size(); ++j) {
                if (grid[i][j] == 1) {
                    q.push(std::make_pair(i, j));
                    paths[i][j] = 0;
                }
            }
        }

        while (not q.empty()) {
            auto point = q.front();
            q.pop();
            for (auto d : dir) {
                int x = point.first + d.first, y = point.second + d.second;
                if (x >= grid.size() or y >= grid.front().size() or x < 0 or y < 0) continue;
                if (paths[point.first][point.second] + 1 < paths[x][y]) {
                    paths[x][y] = paths[point.first][point.second] + 1;
                    q.push(std::make_pair(x, y));
                }
            }
        }

        int result = -1;
        for (auto row : paths) {
            for (auto v : row) {
                result = std::max(result, v);
            }
        }

        return result == INT_MAX ? -1 : result;
    }

    int maxDistance_simple(vector<vector<int>>& grid) {
        std::vector<std::pair<int, int>> lands;
        std::vector<std::pair<int, int>> oceans;
        for (int i = 0; i < grid.size(); ++i) {
            for (int j = 0; j < grid[0].size(); ++j) {
                if (grid[i][j] == 0)
                    oceans.push_back(std::make_pair(i, j));
                else
                    lands.push_back(std::make_pair(i, j));
            }
        }
        if (lands.empty() or oceans.empty()) return -1;

        int result = 0;
        for (auto ocean : oceans) {
            int tmp = INT_MAX;
            for (auto land : lands) {
                tmp = std::min(tmp, abs(ocean.first - land.first) + abs(ocean.second - land.second));
                if (tmp < result) break;
            }
            result = std::max(tmp, result);
        }

        return result;
    }
};

int main() {
    std::vector<std::vector<int>> grid{{1, 0, 1}, {0, 0, 0}, {1, 0, 1}};
    Solution s;
    s.maxDistance(grid);
}
